oo o O (N m c3 ON A THEOREM OF SHKREDOV TOM SANDERS Abstract. We show that if A is a finite subset of an abelian group with ad- ditive energy at least c\A\ 3 then there is a set C C A with \C\ = (^(c -1 log |j4|) such that |AnSpan(£)| = £l(c 1 / 2 \A\). 1. Introduction and notation .^ , We shall prove the following theorem which is a slight strengthening of |Shk07| r \ ' Theorem 1.5]. c"| Theorem 1.1. Suppose that G is an abelian group and A c G is a finite set with \\1a * MIp(g) ^ C \ A \ 3 - Then there is a set £ C A with \C\ = O^ 1 log \A\) such thaR \A n Span(£)| = Sl(cV 2 \A\). It is immediate from the Cauchy-Schwarz inequality that if |.<4 + .A| ^ K\A\ then I! 1a * 1a|!£2( G -) ^ l^4| 3 /^ whence the conclusion of the above result applies to A. This was noted by Shkredov in [Shk07l Corollary 3.2], however, something slightly stronger is also trueo Theorem 1.2. Suppose that G is an abelian group and A C G is a finite set with \A + A\ < K\A\. Then there is a set C C A with \C\ = 0(K log |A|) such that 4cS P an(£). Before we begin with our proofs it will be useful to recall some well-known tools; Rudin |Rud90j is the classic reference for these. A subset C of an abelian group G is said to be dissociated if /\ • 2_. a x- x = Og and a e {—1, 0, 1} £ implies that a = 0. Algebraically, dissociativity is particularly useful in view of the following easy lemma. Lemma 1.3. Suppose that G is an abelian group and A C G is finite. If C C A is a maximal dissociated subset of A then A C Span(£). Analytically, dissociativity can be handled very effectively using the Fourier transform which we take a moment to introduce. Suppose that G is a (discrete) abelian group. We write G for the dual group, that is the compact abelian group of homomorphisms from G to S 1 := {z € C : \z\ = 1} Recall that Span(£) is the set of all sums 5Za;G£ (T».x where a £ {—1, 0, 1} £ Since writing these notes it has independently proved Theorem 11.21 Since writing these notes it has come to the author's attention |Shk| that Shkredov has also TOM SANDERS endowed with the Haar probability measure /ig, and define the Fourier transform of a function / 6 £ 1 (G) to be /:G^C; 7-^/(^)7(3 xEG The following result is a key tool in harmonic analysis. Proposition 1.4 (Rudin's inequality). Suppose that G is an abelian group and C C G is a dissociated set. Then, for each p € [2, 00) we have ll/IU^e) = 0(Vp\\f\\mc)) for all f G £ 2 (£). 2. The proof of Theorem II. II Our proof of Theorem 1 1.1 1 is guided by Shkredov [Shk07] although we are able to make some simplifications by using some standard facts about the L p (/zg)-norms. Wc require the following lemma which is contained in the paper Bou90] of Bourgain. Lemma 2.1. Suppose that G is a abelian group, A c G is finite, I is a positive integer and p ^ 2. Then there is a set A' C A such that all dissociated subsets of A' have size at most I and \\lA-lA>\\L*Qi )=0(y/ P /l\A\). Proof. We define sets A D A x D ■ ■ ■ D A s and £ , C\, . . . ,£ s iteratively starting with A Q := A. Suppose that we have defined Ai. (i) If there is no dissociated subset of Ai with size I then terminate the itera- tion; (ii) if there is a dissociated subset of A4 with size I then let Li be any such set and put Ai + i — Ai\ d. The algorithm terminates at some stage s with s ^ \A\/l since |Aj+i| = \Ai\ — I. Write A' := A s which consequently has no dissociated subset of size greater than I. Since A is the disjoint union of the sets Co, ■ ■ ■ , C s -i and A! we have s-1 s-1 II 1,4- 1a'IUj>0* 8 ) = II^Z 1c 'II Lp ^g) ^ zJll^H^Oe)' Now each summand is 0(y / p||l£ i ||^2(£.)) = 0(\/pl), by Rudin's inequality, whence llO - G\\lHp s ) = 0{s^pl) = 0{^pJl\A\), in view of the upper bound on s. □ Proof of Theorem \l.l\ Write p := 2 + log |.<4| and let I be an integer with I = <3(p C -(p-2)/p|^|2/p) _ ( c -i log ^ such that when we apply LemmaHUto A we get a set A' d A for which (2.1) ||U - QlliP^) < c<*-*>/*>\A\<*-Wv/2. Let £ be a maximal dissociated subset of A'. We have \C\ ^ I = 0(cr l log \A\) by the choice of I, and A' C Span(£) by Lemma [TT3l whence \AC\ Span(£)| ^ \A'\ and the result will follow from a lower bound on \A'\. By the log-convexity of the L p {^,~) norms we have \\U\W e ) < ll^lli 2 C/ (P " } |l^ll-(t) 2) - W^'^llQ^. ON A THEOREM OF SHKREDOV 3 where the equality is by Parseval's theorem. However, we are given that the left hand side is at least c|j4| 3 , whence we get the lower bound (2.2) \\u\\L P{ » s )>c {p ~ 2)/2p \A\ (p - 1)/p . On the other hand using Holder's inequality we have the upper bound llGll^a) < llGll^jllGllfegg < \Ar~ 1)/p , where the second inequality is by Parseval's theorem and the Hausdorff- Young inequality applied to the L 2 -norm and L°°-norm respectively. By the triangle inequality, this and (|2.2|) give IIU - G'hnno) > c^-^/^iai^- 1 )/" - ia'i^-v/p. Using the upper bound on the left hand side from (J2.1D it follows that \A'\ > c (p-2)/2(p-D 2 -p/(p-i)|A| > c l ' 2 \A\/A, as required. □ 3. The proof of Theorem 11.21 The proof is essentially Theorem 6.10 of Lopez and Ross [LR75] coupled with Lemma 11.31 Proof of Theorem[FE Write / := \ A+A * 1_ A , Then Li(Mg) = / IWa(7)1-a(7)MMgW : ( / |l, + i(-l| 2 dMe(7)) f/|C4( 7 )| 2 d/ie(7) V ' = y/\A + A\\-A\^VK\A\, by the Cauchy-Schwarz inequality, Parseval's theorem and the doubling condition \A + A\ s$ K\A\, Furthermore \\f\\i^ {G ) < \A\ and ||/||/i( G ) = \A\\A + A\ and so ll/llWg) = WfWrw < ||/IU»(G).||/IUx(G) < 14V + 4 < tf|A| 3 , by Parseval's theorem, Holder's inequality and the doubling condition. Whence, by log-convexity of the L p (//g) norms, we have \\f\\ LP ' ( , e) ^VK\A\^+^ior & l\p'e[l,2}. Suppose that £ is a maximal dissociated subset of A and (p,p') is a conjugate pair of exponents with p' e (1,2]. Then, by Rudin's inequality we have \\f\\l>(C) = (f 1 C,f}v>(M S ) < \\f 1 c\\LP( Ms )\\f\\ L p'^ e ) = =0(Vp.\\f\\mc)\\f\\ LP ' { , 8) )- The construction of / ensures that for any aei, f(a) — Ia+a * 1— a(o) #* \A\ so, canceling ||/||^2( £ ) above we get Vn\W < ii/ii^(£) = o(vpii/ii^ ( ^)) = o(v^i^i (p,+1)/2 )- Putting p = 2 + log | A| and some rearrangement tells us that |£| = 0(if log |^4|). Since £ was maximal Lemma 11.31 then yields the result. □ TOM SANDERS References [Bou90] J. Bourgain. On arithmetic progressions in sums of sets of integers. In A tribute to Paul Erdos, pages 105-109. Cambridge Univ. Press, Cambridge, 1990. [LR75] J. M. Lopez and K. A. Ross. Sidon sets. Marcel Dekker Inc., New York, 1975. Lecture Notes in Pure and Applied Mathematics, Vol. 13. [Rud90] W. Rudin. Fourier analysis on groups. Wiley Classics Library. John Wiley & Sons Inc., New York, 1990. Reprint of the 1962 original, A Wiley-Interscicnce Publication. [Shk] I. D. Shkrcov. Personal communication. [Shk07] I. D. Shkrcdov. On sets with small doubling. Preprint, 2007. Department of Pure Mathematics and Mathematical Statistics, University of Cam- bridge, WlLBERFORCE ROAD, CAMBRIDGE CB3 0WA, ENGLAND E-mail address: t .sandersadpmms.cam.ac.uk